height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

// var trap = function (height) {
//     let len = height.length
//     if (len === 0) return height

//     let leftHeight = new Array(len) // 当前位置左侧的最高高度
//     let rightHeight = new Array(len) // 当前位置右侧的最高高度

//     leftHeight[0] = height[0]
//     for (let i = 1; i < len; i++) {
//         leftHeight[i] = Math.max(leftHeight[i - 1], height[i])
//     }

//     rightHeight[len - 1] = height[len - 1]
//     for (let i = len - 2; i >= 0; i--) {
//         rightHeight[i] = Math.max(rightHeight[i + 1], height[i])
//     }

//     let sum = 0
//     for (let i = 0; i < len; i++) {
//         let minHeight = Math.min(leftHeight[i], rightHeight[i])
//         sum += minHeight - height[i]
//     }
//     return sum
// };

var trap = function (height) {
    let len = height.length;
    let res = 0;
    let leftHeight = new Array(len), rightHeight = new Array(len);

    leftHeight[0] = height[0];
    for (let i = 1; i < len; i++) {
        leftHeight[i] = Math.max(leftHeight[i - 1], height[i]);
    }

    rightHeight[len - 1] = height[len - 1];
    for (let i = len - 2; i >= 0; i--) {
        rightHeight[i] = Math.max(rightHeight[i + 1], height[i]);
    }

    for (let i = 0; i < len; i++) {
        res += Math.min(leftHeight[i], rightHeight[i]) - height[i]
    }
    return res;
}

console.log(trap(height));
